1. Field of the Invention
This invention relates to resolving locking contention for deadlocked tasks, and more particularly, to resolving locking contention for waiting transactions that are not truly deadlocked.
2. Description of the Related Art
Tasks (also, "processes") are streams of activity. Transactions are particular kinds of tasks that must either be entirely completed or rolled back. When two or more tasks compete for two or more resources, the further execution of either, or both may be blocked. When tasks cannot proceed because of competition for the same resource, they are said to be "deadlocked". A deadlock is typically resolved by termination ("abortion") or rollback of one or more of the deadlocked tasks.
Techniques have been developed to handle or allocate requests from different tasks to access or use a data processing system resource. The task may be a database operation, file or data record request, register access or use, or a memory access request, for example. The resource may be any form of data storage such as a hard disk drive, a floppy drive, a CDROM, a random access memory (RAM), a tape drive, a register or a cache in a microprocessor where individual bytes of data, records, or files may be stored. In other instances, a resource may comprise a series of records stored in any form of the above-mentioned data storage. In addition, the series of records may be stored in several different data storage sites in one data processing system or across multiple data processing systems such as a distributed data processing system.
In order to control access to a resource in a transaction processing system, transactions are required to have a "lock" on the resource before they are granted access to it. To receive a lock on a resource, transactions submit requests for locked use of the resource. A lock mode signifies the kind of lock requested (at least X and S). The status of a request may be at least either GRANTED or WAITING. The lock request may be for exclusive (X) or shared (S) use of the resource. The lock requests may be stored in queues, stacks, linked lists, chains, tables, trees or the like and locks may be granted to transactions on a first in and first out (FIFO) or priority basis or any other basis known in the art. Transactions may require access to several resources before their underlying operations can be completed. For example, a join command (JOIN) in a database application may have to access two tables. In such a case, the transaction submits requests for locks on each of the resources needed to complete the operation. Once the operation is complete, the locks on the resources are released by the transaction.
Lock acquisition is automated in many applications. For example in database applications, a database management system (DBMS) generates the appropriate lock requests for resource use during processing of a database query (or transaction) generated by a user or an application in a distributed data processing system. The lock requests are processed by a lock manager that may include a concurrency control component that detects deadlocks, and a resolution component that resolves detected deadlocks. Deadlock detection and resolution require maintenance and processing of the structures mentioned above.
Different types of transactions may require either shared or exclusive locks on one or more resources to be completed. For example, a JOIN requires shared locks on the resources that contain the records to be joined. An UPDATE, however, requires exclusive access to the resources containing records to be changed. Frequently, multiple transactions require access to the same resource. If two or more transactions need only shared access to the resource, they may be concurrently granted shared locks for the resource. As a consequence, these transactions can execute in parallel (provided all the locks needed for each transaction have been granted.)
As noted above, in order to control access to resources, lock requests are received and processed by a lock manager which serializes access to the resources, based on lock requests. Serialization of access can sometimes prevent access to a resource by any transactions. This may occur, for example, when several transactions request simultaneous access to the same resources, with some of the transactions granted some of the locks but none of the transactions being granted all the locks needed to complete because of contention with the other transactions. When this occurs, the transactions are deadlocked. For example, deadlock commonly occurs when two transactions require access to two or more resources, and each receives a lock to one of the resources. When this occurs, one of the transactions (the "victim") is rolled back or aborted so the other can be granted the lock needed to complete. The victim transaction must release locks held, roll back and then generate new requests for locks on the resources it needs to complete.
To illustrate an example of deadlock between transactions, consider the following scenario: Transaction 1 needs exclusive access to resources A and B to complete, and transaction 2 needs exclusive access to resources B and A to complete. Transaction 1 requests a lock on resource A, while transaction 2 requests a lock on resource B. These lock requests are granted (i.e., transaction 1 receives an exclusive lock on resource A and transaction number 2 receives an exclusive lock for resource B). Then, transaction 1 requests a lock on resource B and transaction 2 requests a lock on resource A. Resource A, however, is exclusively locked by transaction 1 and resource B is exclusively locked by transaction 2. Therefore, neither transaction 1 or 2 can be granted all the locks need to complete and neither transaction will release their current locks until they complete; the transactions are deadlocked.
In order to resolve this deadlock, either transaction 1 or 2 is victimized by rollback or abortion. Then, the victim transaction will release its held lock, allowing the non-victim transaction to be granted the additional lock needed to complete. After the transaction is complete, it will release the locks on resources A and B. Then, the victim transaction's resubmitted requests for exclusive locks for resource A and B can be granted. This, of course, is inefficient, since work must be rolled back. In the preceding example, transactions 1 and 2 would not have been deadlocked if they both needed only shared access to resource A and B. In this scenario shared locks could be granted to both transactions for resources A and B. Then, the transactions could complete simultaneously.
Consider the scenario illustrated in the transaction status table of FIG. 2, where transactions 1 and 2 require shared access to resources A and B and transactions 3 and 4 require exclusive access to resources A and B, respectively. Further, transactions 3 and 4 request exclusive locks for resources A and B immediately after transaction 1 requests and is granted a shared lock for resource A and transaction 2 requests and is granted a shared lock to resource B. Transactions 1 and 2 would again be deadlocked even though they only require shared locks for resource A and B to complete. The request of transaction 3 for an exclusive lock for resource A is located between the requests of transaction 1 and 2 for shared locks for resource A in the status table. Likewise, the request of transaction 4 for an exclusive lock on resource B is located between the request of transaction 2 and 1 for shared locks on resource B. As a consequence, shared locks for resources A and B to transactions 1 and 2 can not be granted since the requests are not contiguous in the queues for these resources. Thus, transactions 1, 2, 3, and 4 are deadlocked, although transaction 1 and 2 are only "pseudo-deadlocked" since they could execute simultaneously because they both require only shared locks on one or more resources. The intervening exclusive lock requests by transactions 3 and 4, however, prevent grouping and assignment of shared locks for transactions 1 and 2. In order to resolve this deadlock, the prior art teaches victimization of either transaction 1 or 2. This permits either transaction 3 or 4 to be granted the exclusive lock on resource A or resource B. The transaction completes, then releases its lock on resource A or resource B. Then, non-victim transaction 1 or 2 can be granted the second shared lock it needs to complete. The transaction completes, and then releases both shared locks. Likewise, either transaction 3 or 4 receives its lock, completes, and releases the lock. Finally, the victim transaction 1 or 2 may be granted shared locks for resource A and B, complete, and release the locks.
This method for resolving locking contention for pseudo-deadlocked transactions is inefficient. The aborted or rolled back transaction must release its held locks and resubmit requests for those locks. In addition, if the lock requests for the resources were managed more efficiently, transactions 1 and 2 could have executed concurrently, since they required only shared locks. Thus, an efficient method or technique is needed to resolve locking contention for pseudo-deadlocked transactions.